/*
 *https://leetcode.cn/problems/maximum-subarray/
 *lc53. 最大子数组和
 *medium 吴朝泽 2024.12.6
 *动态规划
*/

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0], f = nums[0];
        for (int i = 1; i < nums.size(); ++i) 
        {
            f = max(f, 0) + nums[i];
            ans = max(ans, f);
        }
        return ans;
    }
};